home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource5 / 347_01 / tavltree.h < prev    next >
Text File  |  1991-10-21  |  9KB  |  217 lines
  1. #if !defined TAVLtree_H
  2. #define TAVLtree_H
  3.  
  4. /*:file:version:date: "%n    V.%v;  %f"
  5.  * "TAVLTREE.H    V.20;  20-Oct-91,13:38:38"
  6.  *
  7.  *  Threaded-AVL, or threaded height-balanced trees
  8.  *
  9.  *  Purpose:    Threaded AVL trees provide fast access ,O(log N),
  10.  *              to data nodes AND allow efficient ,O(1), sequential
  11.  *              access; i.e., given a node, the next or previous
  12.  *              node can be efficiently accessed.
  13.  *
  14.  *  References: Fundamentals of Data Structures; Horowitz & Sahni
  15.  *              Computer Science Press
  16.  *              See 5.6 (threaded trees) & 9.2 (dynamic tree tables)
  17.  *
  18.  *  Released to the PUBLIC DOMAIN
  19.  *
  20.  *  Author:             Bert C. Hughes
  21.  *                      200 N. Saratoga
  22.  *                      St.Paul, MN 55104
  23.  *                      Compuserve 71211,577
  24.  */
  25.  
  26. /* Constants for "replace" parameter of "tavl_insert" */
  27. #define REPLACE     1
  28. #define NO_REPLACE  0
  29.  
  30. /*  Constants are possible return values of "tavl_setdata" */
  31. #define TAVL_OK          0  /* No error. */
  32. #define TAVL_NOMEM       1  /* Out of memory error */
  33. #define TAVL_ILLEGAL_OP  2  /* Requested operation would disrupt the
  34.                                tavl_tree structure; operation cancelled! */
  35.  
  36. #include <stddef.h>         /* for definition of "NULL" */
  37.  
  38. typedef struct tavlnode *TAVL_nodeptr;
  39. typedef struct tavltree *TAVL_treeptr;
  40.  
  41. /* prototypes */
  42.  
  43. TAVL_treeptr tavl_init(int (*compare)(void *key1, void *key2),
  44.                     void *(*key_of)(void *DataObject),
  45.                     void *(*make_item)(const void *DataObject),
  46.                     void (*free_item)(void *DataObject),
  47.                     void *(*copy_item)(void *Destination_DataObject,\
  48.                                  const void *Source_DataObject),
  49.                     void *(*alloc)(size_t),
  50.                     void (*dealloc)(void *)
  51.                     );
  52.             /*
  53.             Returns pointer to empty tree on success, NULL if insufficient
  54.             memory.  The function pointers passed to "tavl_init" determine
  55.             how that instance of tavl_tree will behave & how it will use
  56.             dynamic memory.
  57.  
  58.                 parameters-
  59.                   compare:      Compares identifiers, same form as "strcmp".
  60.                   key_of:       Gets pointer to a data object's identifier.
  61.                   make_item:    Creates new data object that is a copy of
  62.                                 *DataObject.
  63.                   free_item:    Complements make_item. Releases any memory
  64.                                 allocated to DataObject by "make_item".
  65.                   copy_item:    Copies data object *Source to buffer *Dest
  66.                   alloc:        Memory allocator.
  67.                   dealloc:      Deallocates dynamic memory - complements
  68.                                 "alloc"
  69.             */
  70.  
  71.  
  72. int tavl_setdata(TAVL_treeptr tree, TAVL_nodeptr p, void *item);
  73.             /*
  74.             Replace data contents of *p with *item.
  75.             returns:
  76.                 0  ................ OK
  77.                 TAVL_NOMEM ........ out of memory (heap space)
  78.                 TAVL_ILLEGAL_OP ...
  79.                      (*tree->key_of)(p->dataptr) != (*tree->key_of)(item)
  80.  
  81.             Uses "make_item" and "free_item". See tavl_init.
  82.             */
  83.  
  84. void *tavl_getdata(TAVL_treeptr tree, TAVL_nodeptr p, void *buffer);
  85.             /*
  86.             A safe method of reading the data contained in TAVL_NODE.
  87.             If user/programmer uses "dataptr" for anything other than
  88.             reading the data "dataptr" points to, the tavl_tree will
  89.             be corrupted.  Returns *buffer;  Data will be copied to
  90.             buffer using method "copy_item"; see tavl_init.
  91.             */
  92.  
  93. TAVL_nodeptr tavl_insert(TAVL_treeptr tree, void *item, int replace);
  94.             /*
  95.             Using the user supplied "key_of" & "compare" functions,
  96.             *tree is searched for a node which matches *item. If a
  97.             match is found, the new item replaces the old if & only
  98.             if replace != 0.  If no match is found the item is
  99.             inserted into *tree.  "tavl_insert" returns a pointer to
  100.             the node inserted or found, or NULL if there is not enough
  101.             memory to create a new node and copy "item".  Uses functions
  102.             "key_of" and "compare" for comparisons and to retrieve
  103.             identifiers from data objects, "make_item" to create a copy
  104.             of "item", "alloc" to get memory for the new tree node, and
  105.             "dealloc" if "make_item" fails.
  106.             */
  107.  
  108. int tavl_delete(TAVL_treeptr tree, void *key);
  109.             /*
  110.             Delete node identified by "key" from *tree.
  111.             Returns 1 if found and deleted, 0 if not found.
  112.             Uses "compare", "key_of", "free_item" and "dealloc".
  113.             See function tavl_init.
  114.             */
  115.  
  116. void tavl_delete_all(TAVL_treeptr tree);
  117.             /*
  118.             Remove all data nodes from tree, release memory used.
  119.             */
  120.  
  121. void tavl_destroy(TAVL_treeptr tree);
  122.             /*
  123.             Destroy the tree. Uses functions "free_item" and "dealloc"
  124.             to restore pool memory used. See function tavl_init.
  125.             */
  126.  
  127. TAVL_nodeptr tavl_find(TAVL_treeptr tree, void *key);
  128.             /*
  129.             Returns pointer to node which contains data item
  130.             in *tree whose identifier equals "key". Uses "key_of"
  131.             to retrieve identifier of data items in the tree,
  132.             "compare" to compare the identifier retrieved with
  133.             *key.  Returns NULL if *key is not found.
  134.             */
  135.  
  136. /********************************************************************
  137.     Following three functions allow you to treat tavl_trees as a
  138.     doubly linked sorted list with a head node.  This is the point
  139.     of threaded trees - it is almost as efficient to move from node
  140.     to node or back with a threaded tree as it is with a linked list.
  141. *********************************************************************/
  142.  
  143. TAVL_nodeptr tavl_reset(TAVL_treeptr tree);
  144.             /*
  145.             Returns pointer to begin/end of *tree (the head node).
  146.             A subsequent call to tavl_succ will return a pointer
  147.             to the node containing first (least) item in the tree;
  148.             just as a call to tavl_pred would return the last
  149.             (greatest).  Pointer returned can only be used a parameter
  150.             to "tavl_succ" or "tavl_pred" - the head node contains no
  151.             user data.
  152.             */
  153.  
  154. TAVL_nodeptr tavl_succ(TAVL_nodeptr p);
  155.             /*
  156.             Returns successor of "p", or NULL if "p" has no successor.
  157.             */
  158.  
  159. TAVL_nodeptr tavl_pred(TAVL_nodeptr p);
  160.             /*
  161.             Returns predecessor of "p", or NULL if no predecessor.
  162.             */
  163.  
  164. /**************      END PUBLIC DEFINITIONS     *******************/
  165.  
  166. /* Private: for internal use by tavl*.c library routines only! */
  167.  
  168. /*   See note below
  169.      ... recommended that TAVL_USE_BIT_FIELDS remain commented out,
  170.      ... both for efficiency (speed) and universiality.
  171. #define TAVL_USE_BIT_FIELDS
  172. */
  173.  
  174. typedef struct tavlnode {
  175.             void *dataptr;
  176.             struct tavlnode *Lptr, *Rptr;
  177. #if !defined TAVL_USE_BIT_FIELDS
  178.                                         /* see NOTE below */
  179.             signed  char bf;            /* assumes values -2..+2 */
  180.                     char Lbit;          /* 0 or 1 */
  181.                     char Rbit;          /* 0 or 1 */
  182. #else
  183.             signed   int bf     : 3;    /* assumes values -2..+2 */
  184.             unsigned int Lbit   : 1;
  185.             unsigned int Rbit   : 1;
  186. #endif
  187.         } TAVL_NODE;
  188.  
  189. typedef struct tavltree {
  190.             TAVL_nodeptr head;
  191.             int (*cmp)(void *, void *);
  192.             void *(*key_of)(void *);
  193.             void *(*make_item)(const void *);
  194.             void (*free_item)(void *);
  195.             void *(*copy_item)(void *, const void *);
  196.             void *(*alloc)(size_t);
  197.             void (*dealloc)(void *);
  198.         } TAVL_TREE;
  199.  
  200. /* end private */
  201.  
  202. /* !!! NOTE */
  203.    /*
  204.     * R.Artigas points out that some Standard C compilers do NOT support
  205.     * signed bit fields; in particular, Microsoft C version 5.1 does not.
  206.     *
  207.     * It may also be true that bit field testing is not so efficient
  208.     * as using "char"s for flag variables - it depends on the compiler.
  209.     *
  210.     * By default, TAVLTREE uses char variables for flags in TAVL_NODE.
  211.     * If you wish to use bit fields instead, define "TAVL_USE_BIT_FIELDS".
  212.     */
  213.  
  214. #endif
  215.  
  216.  
  217.